#include <iostream>
#include <string.h>
#include <assert.h>
#include "R_iterator.hpp"
using namespace std;

template<class T>
class Myvector{
  public:
    //iterator
    typedef T *iterator;
    typedef const T *const_iterator;
    typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
    typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
    
    iterator begin(){
      return _start;
    }

    iterator end(){
      return _finish;
    }

    reverse_iterator rbegin(){
      return reverse_iterator(end());
    }

    reverse_iterator rend(){
      return reverse_iterator(begin());
    }

    const_iterator begin() const{
      return _start;
    }
    const_iterator end() const{
      return _finish;
    }

    const_reverse_iterator rbegin() const{
      return const_reverse_iterator(end());
    }

    const_reverse_iterator rend() const{
      return const_reverse_iterator(begin());
    }
    //construct and destroy
    Myvector()
      :_start(nullptr),
      _finish(nullptr),
      _end_of_storage(nullptr)
    {}

    Myvector(size_t n, const T &val = T())
      :_start(nullptr),
      _finish(nullptr),
      _end_of_storage(nullptr)
    {
      resize(n, val);
    }

    Myvector(T n, const T &val = T())
      :_start(nullptr),
      _finish(nullptr),
      _end_of_storage(nullptr)
    {
      resize(n, val);
    }

    template<class input_iterator>
     Myvector(input_iterator first, input_iterator last)
        :_start(nullptr),
        _finish(nullptr),
        _end_of_storage(nullptr)
      {
        reserve(last-first);
        while(first!=last)
        {
          *_finish = *first;
          ++_finish;
          ++first;
        }
      }

    void swap(Myvector<T> &v){
      std::swap(_start,v._start);
      std::swap(_finish,v._finish);
      std::swap(_end_of_storage, v._end_of_storage);
    }

    //Myvector(const Myvector<T> &v)
    //    :_start(nullptr),
    //    _finish(nullptr),
    //    _end_of_storage(nullptr)
    //{
    //  Myvector tmp(v.begin(), v.end());
    //  swap(tmp); 
    //}


    Myvector(const Myvector<T> &v)
        :_start(nullptr),
        _finish(nullptr),
        _end_of_storage(nullptr)
    {
      reserve(v.size());
      for(size_t i = 0; i<v.size(); ++i)
      {
        _start[i] = v._start[i];
      }
      _finish = _start + v.size();
    }

    Myvector<T>& operator=(const Myvector<T> &v){
      Myvector tmp(v);
      swap(tmp);
    }


    ~Myvector(){
      delete[] _start;
    }

    //capacity
    size_t size()const{
      return _finish-_start;
    }

    size_t capacity()const{
      return _end_of_storage-_start;
    }
    
    void reserve(size_t n){
      if(n > capacity())
      {
        iterator tmp = new T[n];
        size_t sz = size();
        if(_start!=nullptr)
        {
          //memcpy(tmp, _start, sz * sizeof(T));
          for(size_t i = 0; i< sz; ++i)
          {
            tmp[i] = _start[i];
          }
          delete[] _start;
        }
        _start = tmp;
        _finish = _start + sz;
        _end_of_storage = _start + n;
      }
    }

    void resize(size_t n, const T &val = T()){
      if(n > size())
      {
        reserve(n);
        for(size_t i = size(); i<n; ++i)
        {
          _start[i] = val;
        }
      }
      _finish = _start + n;
    }

    //access
    T& operator[](size_t pos){
      assert(pos < size());
      return _start[pos];
    }

    const T& operator[](size_t pos)const{
      assert(pos < size());
      return _start[pos];
    }

    //modify
    void push_back(const T &val){
      if(_finish == _end_of_storage)
      {
        size_t n = capacity() == 0? 5:capacity()*2;
        reserve(n);
      }
      *_finish = val;
      ++_finish;
    }
    
    void pop_back(){
      assert(_finish != _start);
      --_finish;
    }

    iterator insert(iterator pos, const T &val){
      assert(pos >= _start);
      assert(pos <= _finish);
      if(_finish == _end_of_storage)
      {
        size_t n = capacity() == 0? 5:capacity()*2;
        size_t len = pos-_start;
        reserve(n);
        pos = _start+len;
      }
      iterator end = _finish - 1;
      while(end >= pos)
      {
        *(end+1) = *end;
        --end;
      }
      *pos = val;
      ++_finish;
      return pos;
    }

    iterator erase(iterator pos){
      assert(pos >= _start);
      assert(pos < _finish);
      iterator tmp = pos+1;
      while(tmp < _finish){
        *(tmp-1) = *tmp;
        ++tmp;
      }
      --_finish;
      return pos;
    }

    T &front(){
      assert(_start != _finish);
      return *_start;
    }

    T &back(){
      assert(_start != _finish);
      return *(_finish-1);
    }


  private:
    iterator _start;
    iterator _finish;
    iterator _end_of_storage;
};

